package linked_list

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

//单向链表---列表的链表表示
//https://studygolang.com/articles/13795
type LinkList struct {
	head *ListNode //头节点
}

//获取长度
//判断head.next是否为空即可
func (s *LinkList) IsEmpty() bool {
	if s.head == nil {
		return true
	}
	return false
}

//获取长度
func (s *LinkList) Length() int {
	cur := s.head
	if cur == nil {
		return 0
	}
	var length int = 0
	//遍历查找: 当前节点不为空则继续
	for cur != nil {
		length++
		cur = cur.Next
	}

	return length
}

//遍历打印链表
//注意点：
//1. 必须使用新指针去遍历，否则会将当前链表修改
//2. 循环判断只需要判断当前节点不为空，则可以继续遍历。新手容易写成判断cur.next不为空，这样最后一个节点会被遗漏，导致没有被遍历
func (s *LinkList) PrintList() {
	cur := s.head //新指针用于遍历
	for cur != nil {
		fmt.Printf("%d ", cur.Val) //先打印
		cur = cur.Next
	}
	fmt.Println("")
}

//转成slice
func (s *LinkList) AsSlice() []int {
	tmp := make([]int, 0)
	cur := s.head //新指针用于遍历
	for cur != nil {
		tmp = append(tmp, cur.Val)
		cur = cur.Next
	}

	return tmp
}

//获取指定元素的位置
func (s *LinkList) GetElem(val int) (int, error) {
	cur := s.head
	var loc int = 0
	//遍历查找
	for cur != nil {
		if cur.Val == val {
			return loc, nil
		}
		cur = cur.Next //后移
		loc++
	}
	return 0, fmt.Errorf("Val not found")
}

//是否包含某个元素
func (s *LinkList) Contain(val int) bool {
	cur := s.head
	for cur != nil {
		if cur.Val == val {
			return true
		} else {
			cur = cur.Next
		}
	}
	return false
}

//链表末尾新增元素
func (s *LinkList) InsertEnd(val int) error {
	//创建一个新节点
	node := &ListNode{
		Val: val,
	}

	//链表为空
	if s.IsEmpty() {
		s.head = node
	} else {
		//先将当前指针挪到末尾，直到cur.next为空
		cur := s.head
		for cur.Next != nil {
			cur = cur.Next
		}

		//next为空则直接追加新节点
		cur.Next = node
	}

	return nil
}

//链表末尾批量新增元素
func (s *LinkList) InsertEndBatch(vals []int) error {

	if len(vals) == 0 {
		return fmt.Errorf("vals is empty")
	}

	cur := s.head

	var node *ListNode

	//为空的情况，需要创建第一个节点
	if s.IsEmpty() {
		for k, v := range vals {
			//创建一个新节点
			node = &ListNode{Val: v}

			if k == 0 {
				s.head = node
				cur = s.head //重新指向head
			} else {
				cur.Next = node
				cur = cur.Next
			}
		}
	} else { //不为空直接追加即可
		//先移到末尾
		for cur.Next != nil {
			cur = cur.Next
		}

		//追加节点
		for _, v := range vals {
			//创建一个新节点
			node = &ListNode{Val: v}

			cur.Next = node
			cur = cur.Next
		}
	}

	return nil
}

//链表头部新增元素
func (s *LinkList) InsertHead(val int) error {
	cur := s.head

	node := &ListNode{
		Val: val,
	}
	node.Next = cur //新元素的next指向当前元素

	s.head = node //当前指针指向 node

	return nil
}

//在loc位置插入元素
func (s *LinkList) InsertElem(loc int, val int) error {
	cur := s.head
	//先挪到loc的位置
	var i int = 1
	for cur.Next != nil && loc > i {
		cur = cur.Next
		i++
	}

	//如果没有找到该位置
	if cur == nil || loc > i {
		//return fmt.Errorf("loc not found")
		//continue 不报错,直接在末尾追加元素
	}

	//找到指定位置, 插入元素
	node := &ListNode{
		Val: val,
	}
	node.Next = cur.Next
	cur.Next = node

	return nil
}

//删除指定位置元素
// 1. 如果头结点就是目标节点，直接删除
// 2. 从第二个节点开始找，直到下一个节点位置==loc说明找到
func (s *LinkList) DeleteElemByLoc(loc int) error {
	if s.head == nil {
		return nil
	}

	cur := s.head

	//删除头节点
	if loc <= 1 {
		s.head = cur.Next
		return nil
	}

	//先找到loc处
	var i int = 1
	for cur.Next != nil && loc > i+1 { //i+1表示下一个节点位置计数
		cur = cur.Next
		i++
	}

	//如果链表遍历结束目标位置仍然不存在
	if cur == nil || loc > i+1 {
		return fmt.Errorf("loc不存在")
	}

	cur.Next = cur.Next.Next

	return nil
}

//删除指定位置元素
//另一种写法
// 1. 如果头结点就是目标节点，直接删除
// 2. 非头结点需要每次查询cur.next位置计数(i+1)和loc是否相等，如果是 i+1 = loc 说明找到目标节点
func (s *LinkList) DeleteElemByLoc2(loc int) error {
	if s.head == nil {
		return nil
	}

	cur := s.head
	if loc <= 1 { //头节点
		s.head = cur.Next
	} else {
		var i int = 1
		for cur.Next != nil {
			if i+1 == loc { //下一个节点是目标节点
				cur.Next = cur.Next.Next
				return nil
			} else {
				cur = cur.Next
				i++
			}
		}

		return fmt.Errorf("loc not found")
	}

	return nil
}

//删除指定元素
// 1. 如果头结点就是目标节点，直接删除
// 2. 非头结点需要每次查询cur.Next.val是否相等，如果是 cur.Next = cur.Next.Next
func (s *LinkList) DeleteElem(val int) error {
	if s.IsEmpty() {
		return nil
	}

	cur := s.head
	if cur.Val == val { //头节点
		s.head = cur.Next
	} else { //非头节点
		for cur.Next != nil {
			if cur.Next.Val == val { //比较下一个节点的值
				cur.Next = cur.Next.Next
				return nil
			} else { //指针继续后移
				cur = cur.Next
			}
		}
	}

	return fmt.Errorf("Val not found")
}
